It is often necessary to generate simplified versions of geometric models. Such simplified models can be used, for example, to display scenes having a polygon count that exceeds the capacity of graphics hardware. The use of simplified models is also advantageous when transmitting a model over a network having a limited bandwidth.
Several algorithms for automatic simplification are currently known in the art. When dealing with curved, finely tessellated surfaces one technique iteratively removes a vertex and incident polygons, and then retessellates the "hole" that is formed. The sequence of vertices considered for removal can be chosen based on simple heuristics or on complex optimization strategies. While this conventional technique normally preserves the topology of the original model its use is, however, restricted to objects with a well defined topology (often to two-manifolds only). Furthermore, this technique cannot, in general, enable a significant reduction in polygon count. Several variants of this method are described in the literature, e.g. by Hughes Hoppe et al. Mesh Optimization, Proc. of SIGGRAPH '93, pp. 19-26.
A different approach is based on collapsing nearby vertices to a single representative vertex, and removing polygons whose area becomes zero. By repeating this process on groups of vertices of increasing size, a hierarchy of simplified models is obtained. This method is fast and can readily handle ill-defined models. The resulting simplified models, however, may not have a desired quality for a particular application. Reference in this regard can be had to commonly assigned U.S. Pat. No. 5,448,686, entitled "Multi-Resolution Graphic Representation Employing at Least One Simplified Model for Interactive Visualization Applications", by Paul Borrel and Jaroslaw R. Rossignac.
While these conventional techniques may be suitable for use for many model simplification problems, it is desirable to provide an improved method that is capable of operating at high speed while providing a simplified model that accurately and faithfully represents an original, more complex model.